热门标签 | HotTags
当前位置:  开发笔记 > 编程语言 > 正文

外心|小步_牛客白月赛21题解

篇首语:本文由编程笔记#小编为大家整理,主要介绍了牛客白月赛21题解相关的知识,希望对你有一定的参考价值。https://ac

篇首语:本文由编程笔记#小编为大家整理,主要介绍了牛客白月赛21题解相关的知识,希望对你有一定的参考价值。




https://ac.nowcoder.com/acm/contest/3947



目录


  • Audio【计算几何 三角形的外心】
  • Channels【容斥】
  • DDoS【拓扑排序】
  • Exams【模拟】
  • Fool Problem【规律】
  • Game【博弈】
  • ”Happy New Year!“
  • I love you【DP】
  • Jelly【BFS】


Audio【计算几何 三角形的外心】


求三角型的外心

#include
using namespace std;
int main()

double x1, x2, x3, y1, y2, y3;
cin>>x1>>y1>>x2>>y2>>x3>>y3;
double A1 = 2 * (x2 - x1),
B1 = 2 * (y2 - y1),
C1 = x2 * x2 - x1 * x1 - y1 * y1 + y2 *y2,
A2 = 2 * (x3 - x2),
B2 = 2 * (y3 - y2),
C2 = x3 * x3 - x2 * x2 - y2 * y2 + y3 * y3;
double x,y;
x=((C1*B2)-(C2*B1))/((A1*B2)-(A2*B1));
y=((A1*C2)-(A2*C1))/((A1*B2)-(A2*B1));
printf("%.3lf %.3lf\\n",x,y);
return 0;


Channels【容斥】


容斥可做,但是细节方面有点不咋会写。于是考虑[1,n] 我们算的话是很容易的。
故我们考虑将区间[l,r] 移动到 [1,n] 的位置。

#include
using namespace std;
typedef long long int LL;
LL l,r;
int main()

while(cin>>l>>r)

LL temp=0;
for(LL i&#61;l;i<&#61;r;i&#43;&#43;)

if(i%60&#61;&#61;0) //找到哪个位置可以整除

temp&#61;i&#43;1;
break;


LL len&#61;(temp-l-10);//将前面不是60整一段多余的计算。
LL sum&#61;max(len,0ll);
r&#61;r-(temp-1);//将区间移动到了[1,r]
sum&#43;&#61;r/60*50;
r&#61;r%60;
sum&#43;&#61;min(r,50ll);
cout<<sum<<&#39;\\n&#39;;

return 0;


DDoS【拓扑排序】

#include
using namespace std;
typedef long long int LL;
const int N&#61;1e5*3&#43;10;
const int mod&#61;20010905;
int h[N],e[N],w[N],ne[N],idx;
LL n,m,d[N],cnt[N];
void add(int a,int b,int c)

e[idx]&#61;b,w[idx]&#61;c,ne[idx]&#61;h[a],h[a]&#61;idx&#43;&#43;;

int main(void)

cin>>n>>m;
memset(h,-1,sizeof h);
while(m--)

int a,b,c; cin>>a>>b>>c;
add(a,b,c);
d[b]&#43;&#43;;

queue<int>q; q.push(1);
cnt[1]&#61;1;
while(q.size())

int u&#61;q.front(); q.pop();
for(int i&#61;h[u];i!&#61;-1;i&#61;ne[i])

int j&#61;e[i];
if(--d[j]&#61;&#61;0) q.push(j);
cnt[j]&#61;(cnt[j]&#43;cnt[u])%mod;


cout<<cnt[n];
return 0;


Exams【模拟】

#include
using namespace std;
const int N&#61;1e5&#43;10;
struct node

int op;
double a;
double x1,y1;
double x2,y2;
double x3,y3;
int sum;
Node[N];
int n;
double sum,ans;
int main(void)

cin>>n;
for(int i&#61;0;i<n;i&#43;&#43;)

cin>>Node[i].op>>Node[i].a;
cin>>Node[i].x1>>Node[i].y1;
cin>>Node[i].x2>>Node[i].y2;
cin>>Node[i].x3>>Node[i].y3;
if(Node[i].op&#61;&#61;2) continue;
sum&#43;&#61;Node[i].a;
Node[i].sum&#61;Node[i].x1*Node[i].y1&#43;Node[i].x2*Node[i].y2&#43;Node[i].x3*Node[i].y3&#43;0.5;

for(int i&#61;0;i<n;i&#43;&#43;)

if(Node[i].op&#61;&#61;2) continue;
ans&#43;&#61;Node[i].a/sum*Node[i].sum;

printf("%.2lf",ans);
return 0;


Fool Problem【规律】

#include
using namespace std;
typedef long long int LL;
int main()

string s; cin>>s;
if(s[s.size()-1]%2&#61;&#61;0) puts("1");
else puts("-1");
return 0;


Game【博弈】


就是看其分解质数的个数。

#include
using namespace std;
typedef long long int LL;
int cnt&#61;0;
int main(void)

LL n; cin>>n;
if(n&#61;&#61;1)

puts("Nancy");
return 0;

for(int i&#61;2;i<&#61;n/i;i&#43;&#43;)

while(n%i&#61;&#61;0) n/&#61;i,cnt&#43;&#43;;

if(n!&#61;1) cnt&#43;&#43;;
cnt--;//减1就是操作的次数
if(cnt&1) puts("Johnson");
else puts("Nancy");
return 0;


”Happy New Year!“

#include
using namespace std;
typedef long long int LL;
int main(void)

puts("Happy New Year!");
return 0;


I love you【DP】

#include
using namespace std;
typedef long long int LL;
const int N&#61;15;
const int mod&#61;20010905;
string a&#61;".iloveyou";
LL f[15];
int main(void)

string s; cin>>s;
for(int i&#61;0;i<s.size();i&#43;&#43;) s[i]&#61;tolower(s[i]);
f[0]&#61;1;
for(int i&#61;0;i<s.size();i&#43;&#43;)

for(int j&#61;1;j<&#61;8;j&#43;&#43;)
if(s[i]&#61;&#61;a[j]) f[j]&#61;(f[j]&#43;f[j-1])%mod;

cout<<f[8];
return 0;


Jelly【BFS】


bfs求最小步数。

#include
using namespace std;
const int N&#61;110;
char a[N][N][N];
int n,st[N][N][N],cnt&#61;1,flag;
int dx[6]&#61;-1,0,0,1,0,0;
int dy[6]&#61;0,-1,1,0,0,0;
int dz[6]&#61;0,0,0,0,-1,1;
int dist[N][N][N];
struct nodeint z,x,y;;
void bfs()

queue<node>q; q.push(1,1,1);
st[1][1][1]&#61;1;
memset(dist,-1,sizeof dist);
dist[1][1][1]&#61;1;
while(q.size())

auto temp&#61;q.front(); q.pop();
int x&#61;temp.x,y&#61;temp.y,z&#61;temp.z;
for(int i&#61;0;i<6;i&#43;&#43;)

int tempx&#61;x&#43;dx[i],tempy&#61;y&#43;dy[i],tempz&#61;z&#43;dz[i];
if(tempx<&#61;0||tempx>n||tempy<&#61;0||tempy>n||tempz<&#61;0||tempz>n) continue;
if(a[tempz][tempx][tempy]&#61;&#61;&#39;*&#39;) continue;
if(st[tempz][tempx][tempy]) continue;
cnt&#43;&#43;,st[tempz][tempx][tempy]&#61;1,dist[tempz][tempx][tempy]&#61;dist[z][x][y]&#43;1;
q.push(tempz,tempx,tempy);



int main(void)

cin>>n;
for(int k&#61;1;k<&#61;n;k&#43;&#43;)
for(int i&#61;1;i<&#61;n;i&#43;&#43;)
for(int j&#61;1;j<&#61;n;j&#43;&#43;)
cin>>a[k][i][j];
bfs();
cout<<dist[n][n][n];
return 0;


推荐阅读
  • golang常用库:配置文件解析库/管理工具viper使用
    golang常用库:配置文件解析库管理工具-viper使用-一、viper简介viper配置管理解析库,是由大神SteveFrancia开发,他在google领导着golang的 ... [详细]
  • 技术分享:从动态网站提取站点密钥的解决方案
    本文探讨了如何从动态网站中提取站点密钥,特别是针对验证码(reCAPTCHA)的处理方法。通过结合Selenium和requests库,提供了详细的代码示例和优化建议。 ... [详细]
  • 1:有如下一段程序:packagea.b.c;publicclassTest{privatestaticinti0;publicintgetNext(){return ... [详细]
  • Explore how Matterverse is redefining the metaverse experience, creating immersive and meaningful virtual environments that foster genuine connections and economic opportunities. ... [详细]
  • 火星商店问题:线段树分治与持久化Trie树的应用
    本题涉及编号为1至n的火星商店,每个商店有一个永久商品价值v。操作包括每天在指定商店增加一个新商品,以及查询某段时间内某些商店中所有商品(含永久商品)与给定密码值的最大异或结果。通过线段树分治和持久化Trie树来高效解决此问题。 ... [详细]
  • Java 中的 BigDecimal pow()方法,示例 ... [详细]
  • 深入理解 SQL 视图、存储过程与事务
    本文详细介绍了SQL中的视图、存储过程和事务的概念及应用。视图为用户提供了一种灵活的数据查询方式,存储过程则封装了复杂的SQL逻辑,而事务确保了数据库操作的完整性和一致性。 ... [详细]
  • 本文详细介绍了 Dockerfile 的编写方法及其在网络配置中的应用,涵盖基础指令、镜像构建与发布流程,并深入探讨了 Docker 的默认网络、容器互联及自定义网络的实现。 ... [详细]
  • 使用Numpy实现无外部库依赖的双线性插值图像缩放
    本文介绍如何仅使用Numpy库,通过双线性插值方法实现图像的高效缩放,避免了对OpenCV等图像处理库的依赖。文中详细解释了算法原理,并提供了完整的代码示例。 ... [详细]
  • Docker的安全基准
    nsitionalENhttp:www.w3.orgTRxhtml1DTDxhtml1-transitional.dtd ... [详细]
  • 本文介绍如何使用 Python 将一个字符串按照指定的行和元素分隔符进行两次拆分,最终将字符串转换为矩阵形式。通过两种不同的方法实现这一功能:一种是使用循环与 split() 方法,另一种是利用列表推导式。 ... [详细]
  • 优化ListView性能
    本文深入探讨了如何通过多种技术手段优化ListView的性能,包括视图复用、ViewHolder模式、分批加载数据、图片优化及内存管理等。这些方法能够显著提升应用的响应速度和用户体验。 ... [详细]
  • Java 中 Writer flush()方法,示例 ... [详细]
  • 深入理解Cookie与Session会话管理
    本文详细介绍了如何通过HTTP响应和请求处理浏览器的Cookie信息,以及如何创建、设置和管理Cookie。同时探讨了会话跟踪技术中的Session机制,解释其原理及应用场景。 ... [详细]
  • CentOS7源码编译安装MySQL5.6
    2019独角兽企业重金招聘Python工程师标准一、先在cmake官网下个最新的cmake源码包cmake官网:https:www.cmake.org如此时最新 ... [详细]
author-avatar
吾车吾家
这个家伙很懒,什么也没留下!
PHP1.CN | 中国最专业的PHP中文社区 | DevBox开发工具箱 | json解析格式化 |PHP资讯 | PHP教程 | 数据库技术 | 服务器技术 | 前端开发技术 | PHP框架 | 开发工具 | 在线工具
Copyright © 1998 - 2020 PHP1.CN. All Rights Reserved | 京公网安备 11010802041100号 | 京ICP备19059560号-4 | PHP1.CN 第一PHP社区 版权所有